#include "../tools.h"
#include <queue>
using std::priority_queue;

// class Cmp{
// public:
//     bool operator()(const ListNode* a, const ListNode* b){
//         return a->val > b->val;
//     }
// };

class Solution {
public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int size = lists.size();
        if(size == 0) return nullptr;
        if(size == 1) return lists[0];

        auto Cmp = [](const ListNode* a, const ListNode* b){return a->val > b->val;};
        priority_queue<ListNode*, vector<ListNode*>, decltype(Cmp)> qMin(Cmp);
        for(int i = 0; i < size; ++i){
            if(lists[i] != nullptr) qMin.push(lists[i]);
        }
            
        ListNode headpre;
        ListNode* res = &headpre;
        while(!qMin.empty()){
            auto tmp = qMin.top();
            res->next = tmp;
            res = res->next;
            qMin.pop();
            if(tmp->next != nullptr)
                qMin.push(tmp->next);
        }

        return headpre.next;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    ListNode* l1 = create_list({1,4,5});
    ListNode* l2 = create_list({1,3,4});
    ListNode* l3 = create_list({2,6});
    
    vector<ListNode*> lists = {l1, l2, l3};
    ListNode* res = sol.mergeKLists(lists);
    show(res);

    return 0;
}

